403 . 樹直徑

Description

小風手上有一棵 $N$$N$ 個點的樹，顧名思義，它有 $N-1$$N-1$ 條邊連接著 $N$$N$ 個點，使得任意兩個點都可以透過若干條邊抵達，節點以 $1$$1$ 至 $N$$N$ 編號。

小風覺得這棵樹太長了，所以他想進行如下操作一次：砍掉樹上的其中一條邊，再另外加上一條邊回去使其保持連通。小風想要透過這個操作減少樹的直徑，請問小風可以透過這個操作讓樹直徑最小為何？

對任意兩點，我們定義其距離為這兩個點之間唯一路徑的邊數，對一個樹我們定義其直徑為任意兩點之間距離的最大值。

Input Format

輸入第一行只有一個正整數 $N$$N$，代表樹上節點的個數。

接下來有 $N-1$$N-1$ 行，第 $i$$i$ 行有兩個正整數 $u,v$$u,v$ 以空白分開，代表第 $i$$i$ 條邊連接的兩個節點編號

• $2\le N\le 5\times {10}^5$$2\le N \le 5\times 10^5$
• $1\le u_i,v_i\le N$$1 \leq u_i, v_i \leq N$
• 輸入保證形成一個樹

Output Format

請輸出一個正整數於一行代表答案。

Sample Input 1

1
5
2
5 1
3
4 1
4
5 3
5
2 3

Sample Output 1

xxxxxxxxxx
1
1
3

Sample Input 2

xxxxxxxxxx
6
1
6
2
6 5
3
1 3
4
3 2
5
4 5
6
6 3

Sample Output 2

xxxxxxxxxx
1
1
3

Sample Input 3

xxxxxxxxxx
10
1
10
2
8 3
3
2 8
4
7 9
5
6 5
6
4 6
7
9 1
8
3 10
9
3 5
10
2 9

Sample Output 3

xxxxxxxxxx
1
1
4

Subtasks

Testdata and Limits